package com.ds.bintree.LeetCode;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: Morris算法
 * @date 2022/9/19 14:29
 */

import java.util.ArrayList;
import java.util.List;

/**
 * Morris其实解决了一个常规循环中循环到叶子节点后难以回到根节点的问题。
 * 我们都知道前序遍历是先左后右，那么对任一节点p1来说，其右子树p1right所有节点必然在左子树p1left之后。
 * 代码中第二个while做的是，在p1left里一直往右，直到找不到更右的点，记这一点为p2。
 * 然后把p1right接到p2的右边。 这样既保证了p1right在p1left所有点之后，又不需要再回到p1节点。
 * 即在正常的往下循环的过程中，不断把右半部分剪下来，接到左半部分的最右下
 */

public class Num144_PreorderTraversal3 {
    //个人理解Morris的思想就是借助树的空闲指针将树链表化
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        while(root != null){
            //前序遍历添加根节点
            res.add(root.val);
            //左子树不为空，按照前序遍历规则先遍历左子树
            //遍历前先将左子树在前序遍历的最后一个节点指向根节点的右子树。
            //前序遍历的最后一个节点：1、是叶节点，2、优先右子树，如果没有右子树再找左子树
            if(root.left != null){
                TreeNode precessor = root.left;
                //1、是叶节点才终止循环
                while(precessor.right != null || precessor.left != null){
                    //2、优先右子树，如果没有右子树再找左子树
                    if(precessor.right != null){
                        precessor = precessor.right;
                    }else{
                        precessor = precessor.left;
                    }
                }
                //最后一个节点指向根节点的右子树
                precessor.right = root.right;
                //先遍历左子树
                root = root.left;
            }else{
                //左子树为空，按照前序遍历规则遍历右子树。
                root = root.right;
            }
        }
        return res;
    }
}
